package com.example.system.class22;

/**
 * @Date 2022/8/21
 * @Author Jonathan
 * @Description 硬币问题 每个硬币只有一枚
 */
public class Code02_CoinsWayEveryPaperDifferent {
    public static void main(String[] args) {
        int[] coins = {1, 4, 1};
        int aim = 2;
        System.out.printf("凑齐%d的方法有:%d种\n", aim, ways(coins, aim));
    }

    /**
     * @param coins 是货币数组
     */
    public static int ways(int[] coins, int aim) {
        return process(coins, 0, aim);
    }


    public static int process(int[] coins, int index, int rest) {
        if (rest < 0) {
            return 0;
        }
        if (index == coins.length) {
            return rest == 0 ? 1 : 0;
        }

        return process(coins, index + 1, rest - coins[index]) + // 要了index位置的硬币
                process(coins, index + 1, rest);  // 没要index

    }

    // 动态规划方法
    public static int dp(int[] coins, int aim) {
        return 0;
    }

}
